(a) Field of the Invention
The present invention relates to a transmission scheduling apparatus and method in a wireless multi-hop network and, more particularly, to a transmission scheduling apparatus and method based on time division multiplex access in a wireless multi-hop network.
(b) Description of the Related Art
An ad-hoc network, a type of a wireless multi-hop network, has been proposed for packet communication sharing a single radio channel. The ad-hoc network can provide a flexible communication service to geographically distributed nodes by using a radio channel as a medium of broadcasting.
The ad-hock network includes multi-hop nodes, and the respective nodes have connectivity with neighboring nodes within communication coverage by sharing a radio channel, thus being able to perform direct communication. Each node may store a packet received from a node and transfer and relay the packet to a different node.
In this manner, since the nodes in the ad-hoc network share a single radio channel through a multi-access scheme, uncontrolled packet transmission may cause a packet collision to damage packets and interfere with packet transmission, resultantly having a negative influence on a transfer rate of the overall network. Thus, all the nodes in the ad hoc network are to be allocated a transmission opportunity based on appropriate time division to avoid collision of packets.
In order to prevent collision of packets, a time division multiple access (TDMA) scheme is used for allocating a transmission opportunity of each node. A TDMA-based ad hock network defines a time axis by a frame having a certain length. In the TDMA-based ad hoc network, broadcasting scheduling is performed such that every node is allocated one or more transmission opportunities from a scheduling table including a certain number of frames, and two mobile nodes located at a one-hop or two-hop distance may not be allocated a transmission opportunity simultaneously.
In relation to an optimized broadcast scheduling algorithm (BSA), research has been actively ongoing since the mid-1980s. Meanwhile, non-deterministic polynomial-time (NP) complete of a broadcast scheduling problem (BSP) was verified in an optimization scheduling process through a distributed greedy algorithm, and a scheduling method including two steps through a mean field annealing (MFA) algorithm has been proposed.
The MFA algorithm is a scheduling method of deriving a minimum number of frames implementable through a node having a maximum number of neighbor nodes, and allowing a maximum number of nodes to be allocated a transmission opportunity in a next stage.
Following the MFA algorithm, sequential vertex coloring (SVC), a Hopfield neural network genetic algorithm (HNNGA), and the like have been used as the BSA.
In the related art BSA, performance of a scheduling table is evaluated on the basis of the Pollaczek-Khintchine formula, and here, the performance of a scheduling table on the basis of the Pollaczek-Khintchine formula refers to a mathematically calculated average packet transmission delay time.
In terms of the characteristics of the Pollaczek-Khintchine formula, the related art BSA makes completion of a scheduling table having a shortest frame length by applying the same packet arrival rate to every node, as a first condition of optimized scheduling, and makes maximization of channel utilization allowing a maximum number of nodes to be allocated a time slot after the shortest frame length is determined, as a second condition.
In this manner, the related art BSA presupposes that every node existing in a network has identical packet transfer quantity without consideration of location and connection information of the nodes. However, in an actual ad-hoc network, network topology is frequently changed due to mobility of nodes, and since communication is performed between nodes through a multi-hop relay, a phenomenon in which packets are concentrated to a node located at the center of the network or a node having a greater number of neighbor nodes occurs frequently. A bottleneck phenomenon resulting from such a phenomenon degrades the packet transfer rate of the overall network.